package leetcode.Y2024M6.study;

import leetcode.Y2024M6.TreeNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class S106 {
    private Map<Integer,Integer> dict=new HashMap<>();
    private int[] postOrder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postOrder=postorder;
        for (int i = 0; i < inorder.length; i++) {
            dict.put(inorder[i],i);
        }

        return buildTree(0,inorder.length-1,0,postorder.length-1);
    }

    private TreeNode buildTree(int is, int ie, int ps,int pe) {
        if (ie<is||pe<ps) return null;
        int root=postOrder[pe];
        int ri=dict.get(root);
        TreeNode node=new TreeNode(root);
        node.left=buildTree(is,ri-1,ps,ps+ri-is-1);
        node.right=buildTree(ri+1,ie,ps+ri-is,pe-1);
        return node;
    }

    @Test
    public void test(){
        int[] inorder={9,3,15,20,7};
        int[] postorder={9,15,7,20,3};
        TreeNode node = buildTree(inorder, postorder);
        System.out.println(node);
    }
}
